home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / INFO / PCCDEMO.ZIP / COMP1.EXE / BACKTRAK.PRS < prev    next >
Text File  |  1993-12-20  |  7KB  |  111 lines
  1.                                                   üÇéèôæÇéèêìå ╬╠╬╠╬╠╬╠╧╧╬╠╡
  2.  
  3.       │     │         │ .          │     Backtracking is a very general
  4.       ├┐┌┐┌┐│┌├ ┌┐┌┐┌┐│┌┬┌┐┌┐      │  technique that is used to solve a
  5.       ││┌┤│ ├┤│ │ ┌┤│ ├┤│││││      │  wide  variety  of  problems  that
  6.       └┘└┘└┘└└└┘┴ └┘└┘└└┴└└└┤      │  exist   in    Computer   Science,
  7.                            └┘      │  especially   in   the   field  of
  8.    ßαΓΩ≤±αΓΩΦφµ  Φ≥  εφΣ  εσ  ≤τΣ  │  Artificial   Intelligence   (AI).
  9. σ⌠φπα∞Σφ≤αδ ΣδΣ∞Σφ≤≥ εσ ∩±εδεµ, α  │  This may be seen by the fact that
  10. δαφµ⌠αµΣ  Φφ  ÷τΦΓτ  ∞αφ√  Σ≈∩Σ±≤  │  the  very  languages  Lisp, along
  11. ≥√≥≤Σ∞≥   αφπ   φα≤⌠±αδ  δαφµ⌠αµΣ  │  with its  many  dialects  such as
  12. ∩±εΓΣ≥≥Φφµ   ≥√≥≤Σ∞≥   τα⌡Σ  ßΣΣφ  │  Scheme, and  PROLOG  comprise the
  13. Φ∞∩δΣ∞Σφ≤Σπ.                       │  linga   franca    of   Artificial
  14.                                    │  Intelligence  and   yet  have  at
  15.                                    │  their  very  core  recursion  and
  16.                                    │  backtracking.
  17.            ß√ πα⌡Φπ ∞. ÷ΦδδΦα∞≥    │
  18.           DipMin BCompSc AACS PCP  │     As   a   general   definition,
  19.                                    │  ßαΓΩ≤±αΓΩΦφµ Φ≥  ≤τΣ ≤ΣΓτφΦ≡⌠Σ εσ
  20.                                    │  µεΦφµ ßαΓΩ÷α±π≥  ε⌡Σ± εφΣ'≥ ≥≤Σ∩≥
  21.                                    │  Φφ ε±πΣ±  ≤ε Σ≈∩δε±Σ  α φΣ÷ ∩α≤τ,
  22.                                    │  ε± ∞Σ≤τεπ εσ  ≥εδ⌡Φφµ ≤τΣ ∩±εßδΣ∞
  23.                                 
  24.  
  25. α≤ ταφπ. This  may continue until  │  Minotaurs chasing you, a possible
  26. either one  solution  is reached,  │  technique is to stick to one wall
  27. or  every  possible  solution  is  │  and  take  every  left  turn  (or
  28. discovered, or  even  until every  │  every right  turn, as  long as we
  29. possible  alternative   has  been  │  are consistent throughout).
  30. explored  with  none  providing a  │     However we wish  to find every
  31. solution.                          │  possible path  through  the maze,
  32.                                    │  and  not  merely  stop  with one.
  33.    As an example,  one might like  │  Therefore,   from   our  starting
  34. to consider  a  general algorithm  │  position we wish to explore paths
  35. for  finding  a  path  through  a  │  that  lead  in   all  four  major
  36. maze. That is, if we imagine that  │  compass  directions  (provided  a
  37. we are trapped in the centre of a  │  path exists  in  that direction).
  38. maze, how is  it possible to find  │  From every  possible  position we
  39. every path that leads back to the  │  could be in along these paths, we
  40. outside world? Well,  if you just  │  wish to  explore paths  that lead
  41. happen to be  Theseus you trail a  │  in   all   four   major   compass
  42. string behind you  on the way in,  │  directions also.
  43. and then trace it back out again.  │  This  leads  us   to  the  simple
  44.    Of  course,  if  there  are no  │  algorithm :
  45.  
  46.  
  47.                                    │  always searching a  maze that has
  48. To  search   a  maze   (from  the  │  been   partially   searched.  The
  49. current position) ...              │  computer  maintains  a  stack  of
  50.                                    │  copies of the maze - one for each
  51. mark the current position as part  │  of   the    partially   completed
  52. of the way out;                    │  procedure calls.  Each copy shows
  53.                                    │  the path  that  has  led  to that
  54. if we're  at the  exit, print the  │  particular location. If we happen
  55. maze (with the path taken so far)  │  to be  at the  exit of  the maze,
  56.                                    │  then the current copy of the maze
  57.      else  if  we  can,  search a  │  shows the way out.
  58. maze (starting one step left);     │
  59.             if  we can,  search a  │     If we do  not get  to an exit,
  60. maze (starting one step up);       │  nothing happens  at  all. Suppose
  61.             if  we can,  search a  │  we take a  left turn  into a dead
  62. maze (starting one step right);    │  end. Since  we  are unable  to go
  63.             if  we can,  search a  │  left,  forward   or  right,  that
  64. maze (starting one step down);     │  particular   invocation   of  the
  65.                                    │  procedure ends,  and its  copy of
  66.    In  this   algorithm,  we  are  │  the maze (with an incorrect path)
  67.  
  68.  
  69. is removed. Thus,  this serves as  │  conflicting    with    previously
  70. a good example of backtracking.    │  placed  queens  then  the current
  71.                                    │  chessboard   is   wrong   and  we
  72.    A second  classic backtracking  │  backtrack -  that is,  attempt to
  73. problem  is   that   of   the  "8  │  place the  previously most recent
  74. Queens", or  more  generally, the  │  queen in its column again.
  75. "n-Queens".  In  this  situation,  │     Otherwise,  if  we  happen  to
  76. one must  determine  all  ways to  │  place a queen  in the last column
  77. place n non-taking  queens on a n  │  then we have succeeded. Following
  78. by n  chessboard.  To  solve this  │  this article is an implementation
  79. problem, one  must begin  with an  │  in LISP of this problem.
  80. empty chessboard  and  attempt to  │
  81. build  up  a  solution  column by  │     Many other famous backtracking
  82. column,   beginning    with   the  │  problems  exist,   such   as  the
  83. leftmost.   Again   the  computer  │  "Knight's Tour".
  84. maintains a  stack  of  copies of  │     Here a chessboard is again the
  85. the  chessboard  with  queens  in  │  scene,  but  this  time  one must
  86. various  positions.   If  we  are  │  take a  Knight around  the entire
  87. unable  to  place  a  queen  in a  │  board such that it lands on every
  88. column    as    it    is   always  │  square,  and   each  square  only
  89.  
  90.  
  91. once. Can a path be found? If one  │  turns, regardless of  how far one
  92. uses backtracking techniques, the  │  must revert in  order to set foot
  93. answer is a resounding 'Yes!'.     │  in the correct direction again.
  94.                                    │
  95.    Of course, the applications of  │     Backtracking  is  certainly  a
  96. backtracking are more than merely  │  useful tool  in the  repetoire of
  97. solving trivial  little problems.  │  the  Computer  Scientist  and its
  98. ßαΓΩ≤±αΓΩΦφµ Γε∞Σ≥ Φφ≤ε ∩δα√ ÷τΣφ  │  use and  ramifications  should be
  99. εφΣ  ⌠≥Σ≥  αφ√   σε±∞  εσ  ≥Σα±Γτ  │  carefully     investigated    and
  100. αδµε±Φ≤τ∞ ≥⌠Γτ α≥ πΣ∩≤τ-σΦ±≥≤, ε±  │  understood ñ
  101. ß±Σαπ≤τ-σΦ±≥≤.  As   has  already  │
  102. been stated,  backtracking is one  │
  103. of  the  fundamental  elements of  │
  104. PROLOG, a language  in which many  │
  105. expert   systems    and   natural  │
  106. language processing  systems have  │
  107. been implemented.  Even compilers  │
  108. may     take     advantage     of  │
  109. backtracking  -   in   short,  it  │
  110. allows one to  recover from wrong  │
  111.